home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / cgazv4n2.zip / MSRCH.C < prev    next >
C/C++ Source or Header  |  1989-08-20  |  14KB  |  494 lines
  1. /***************************************************************
  2.  * File: msrch.c
  3.  * Author: John Rex
  4.  * Purpose: search text for multiple keywords simultaneously
  5.  * Compilers: Turbo C 2.0
  6.  *            Microsoft C 5.1
  7.  * Memory model: any
  8.  *
  9.  * Switches: TEST - if == 1, a test driver is compiled
  10.  *             MAXCHAR - max number of different symbols recognized
  11.  *
  12.  * Usage: The sample driver illustrates all of the key points.  In brief,
  13.  *        there are three routines:
  14.  *            void msrch_int(struct kword *);
  15.  *            void msrch_go(int (*msrch_data) (), void (*msrch_signal) (char *));
  16.  *            void msrch_end(void);
  17.  *
  18.  *          (1) Pass msrch_init() a list of words to search for 
  19.  *        (2) msrch_go() does the work.  It uses pointers to two functions--
  20.  *             the first retrieves a character and the second is called when
  21.  *             a match has been found 
  22.  *        (3) msrch_end() cleans up the work areas
  23.  *
  24.  * Technique: A finite state string pattern matching machine that
  25.  *            recognizes the desired word(s) is built and then used
  26.  *            to scan the text.  See text for detailed discussion.
  27.  *
  28.  * Reference: Aho AV, Corasick MJ: Efficient string matching: An aid to
  29.  *            bibiliographic search.  Comm ACM 1975; 18:333-340.
  30.  *
  31.  **************************************************************/
  32.  
  33. #ifdef DEBUG
  34. #define TELLME(x) x
  35. #else
  36. #define TELLME(x)
  37. #endif
  38.  
  39. #define TEST 0              /* set to 1 to get test driver */
  40. #pragma page
  41. /* local declarations */
  42.  
  43. #include "msrch.h"
  44.  
  45. #define MAXCHAR     256        /* max number of different chars we search for */
  46. static int maxstate;        /* max number of states we have room for */
  47.  
  48. /*******************************************************
  49.  * match_array[] and goto_array[] are the Goto function
  50.  *******************************************************/
  51. static int *match_array;    /* first level of matching.  Possible values:
  52.                                 (1) EMPTY_SLOT
  53.                                 (2) a character
  54.                                 (3) MULTI_WAY       */
  55. #define MULTI_WAY    -1        /* flag for match_array */
  56. #define EMPTY_SLOT    -2        /* flag for match_array */
  57.  
  58. union goto_table {            /* values in match_array take us here */
  59.     int goto_state;            /* directly here if match_array is a character */
  60.     int *branch_table;        /* or to this MULTI_WAY branching table */
  61. } static *goto_array;
  62.  
  63. #define FAIL_STATE    -1        /* in goto_state or branch_table,
  64.                                 this means failure */
  65.  
  66. /*******************************************************
  67.  * out_array[] is the Output function
  68.  *******************************************************/
  69. static struct kword **out_array;    /* list of keywords 'found' by states */
  70.  
  71. /*******************************************************
  72.  * fail_array[] is the Fail function
  73.  *******************************************************/
  74. static int *fail_array;        /* failure transition array */
  75.  
  76. #include <stdio.h>
  77. #include <stdlib.h>
  78. #include <string.h>
  79. #pragma page
  80. /*****************************************************************
  81.  * msrch_init() and subroutines
  82.  * Purpose: setup tables needed by msrch_go()
  83.  ****************************************************************/
  84.  
  85. static int highstate;        /* common variable to track next free state */
  86.  
  87. /* functions we use */
  88. static void enter(unsigned char *), add_state_trans(int, int, int);
  89. static void compute_fail(void);
  90.  
  91. void msrch_init(struct kword *klist)
  92. {
  93.     int i;
  94.     struct kword *ktemp;
  95.  
  96.     /* compute max number of states possible */
  97.     maxstate = 1;
  98.     for (ktemp=klist; ktemp != NULL; ktemp = ktemp->next)
  99.         maxstate += strlen(ktemp->word);
  100.  
  101.     /* allocate space for arrays */
  102.     match_array = (int *) malloc(sizeof(int) * maxstate);
  103.     goto_array = (union goto_table *) malloc(sizeof(union goto_table) * maxstate);
  104.     out_array = (struct kword **) malloc(sizeof(struct kword *) * maxstate);
  105.     fail_array = (int *) malloc(sizeof(int) * maxstate);
  106.  
  107.     /* initialize state arrays */
  108.     for (i=0; i<maxstate; i++) { 
  109.         match_array[i] = EMPTY_SLOT;
  110.         out_array[i] = NULL;
  111.     }
  112.  
  113.     /* initialize state_array[0] */
  114.     highstate = 0;
  115.     add_state_trans(0, 'a', FAIL_STATE);
  116.     add_state_trans(0, 'b', FAIL_STATE);    /* force a multiway table */
  117.  
  118.     /* step thru keywords */
  119.     for(; klist != NULL; klist = klist->next)
  120.         enter(klist->word);
  121.  
  122.     /* setup return to zero transitions for state[0] */
  123.     for (i=0; i<MAXCHAR; i++)
  124.         if (goto_array[0].branch_table[i] == FAIL_STATE)
  125.             goto_array[0].branch_table[i] = 0;
  126.  
  127.     /* and compute failure array */
  128.     compute_fail();
  129. }
  130. #pragma page
  131. static void add_state_trans(int oldstate, int matchchar, int newstate)
  132. /* add transition from oldstate -> newstate for matchchar */
  133. {
  134.     int i, *temp;
  135.  
  136.     /* is this slot empty? */
  137.     if (match_array[oldstate] == EMPTY_SLOT) { /* this is easy */
  138.         match_array[oldstate] = matchchar;
  139.         goto_array[oldstate].goto_state = newstate;
  140.     }
  141.  
  142.     /* is there already a multi-way table? */
  143.     else if (match_array[oldstate] == MULTI_WAY) /* this is easy, too */
  144.         goto_array[oldstate].branch_table[matchchar] = newstate;
  145.  
  146.     /* need to convert to multi-way table */
  147.     else {
  148.         temp = (int *) malloc(sizeof(int) * MAXCHAR);
  149.         for (i=0; i<MAXCHAR; i++)
  150.             temp[i] = FAIL_STATE;
  151.  
  152.         /* copy data from single way branch */
  153.         temp[match_array[oldstate]] = goto_array[oldstate].goto_state;
  154.         
  155.         /* and new data */
  156.         temp[matchchar] = newstate;
  157.  
  158.         /* and load it all into state_array */
  159.         match_array[oldstate] = MULTI_WAY;
  160.         goto_array[oldstate].branch_table = temp;
  161.     }
  162. }
  163. #pragma page
  164. static void enter(unsigned char *kword)
  165. /* add kword to list of words our machine recognizes */
  166. {
  167.     int state, k;
  168.     char *save;
  169.     struct kword *ktemp;
  170.  
  171.     state = 0;
  172.     save = kword;    /* keep a copy */
  173.  
  174.     /* first, see if we can place this word on top of an existing one */
  175.     for (;*kword != '\0'; kword++) {
  176.         /* is this a single char slot? */
  177.         if (match_array[state] == *kword)
  178.             state = goto_array[state].goto_state;
  179.  
  180.         /* multi-way? */
  181.         else if (match_array[state] == MULTI_WAY) {
  182.             if ((k = goto_array[state].branch_table[*kword]) == FAIL_STATE)
  183.                 break;
  184.             else
  185.                 state = k;    /* we have a transition for this char */
  186.         }
  187.  
  188.         /* no match for this char */
  189.         else break;
  190.     }
  191.  
  192.     /* now add new states as needed */
  193.     for (;*kword != '\0'; kword++) {
  194.         highstate += 1;
  195.         if (highstate >= maxstate) { /* uh-oh ... */
  196.             fputs("msrch.c: INTERNAL ERROR - too many states\n", stderr);
  197.             exit(1);
  198.         }
  199.         add_state_trans(state, *kword, highstate);
  200.         state = highstate;
  201.     }
  202.  
  203.     /* now add this keyword to output list for final state */
  204.     ktemp = (struct kword *) malloc(sizeof(struct kword));
  205.     ktemp->word = save;
  206.     ktemp->next = out_array[state];
  207.     out_array[state] = ktemp;
  208. }
  209. #pragma page
  210. static void queue_add(int *queue, int qbeg, int new);
  211. static void find_fail(int state, int s, int a);
  212.  
  213. static void compute_fail()
  214. /* build fail_array and update output_array */
  215. {
  216.     int *queue, qbeg, r, s;
  217.     int i;
  218.  
  219.     /* allocate a queue */
  220.     queue = (int *) malloc(sizeof(int) * maxstate);
  221.     qbeg = 0;
  222.     queue[0] = 0;
  223.  
  224.     /* scan first level and setup initial values for fail_array */
  225.     for (i=0; i<MAXCHAR; i++) 
  226.         if ((s = goto_array[0].branch_table[i]) != 0) {
  227.             fail_array[s] = 0;
  228.             queue_add(queue, qbeg, s);
  229.         }
  230.  
  231.     /* now scan lower levels */
  232.     while (queue[qbeg] != 0) {
  233.         r = queue[qbeg];    /* pull off state from front of queue */
  234.         qbeg = r;            /* and advance qbeg */
  235.  
  236.         TELLME(printf("Now investigating state %d\n",r);)
  237.         /* now investigate this state */
  238.         if (match_array[r] == EMPTY_SLOT)
  239.             continue;        /* no more to do */
  240.         else if (match_array[r] == MULTI_WAY) {
  241.             /* scan its subsidiary states */
  242.             for(i=0; i<MAXCHAR; i++)    /* scan branch_table */
  243.                 if ((s = goto_array[r].branch_table[i]) != FAIL_STATE) {
  244.                     queue_add(queue, qbeg, s);    /* add new state to queue */
  245.                     find_fail(fail_array[r], s, i);
  246.                 }
  247.         }
  248.         else { /* single char */
  249.             queue_add(queue, qbeg, goto_array[r].goto_state);
  250.             find_fail(fail_array[r], goto_array[r].goto_state, match_array[r]);
  251.         }
  252.     }
  253.  
  254.     /* tidy up */
  255.     free(queue);
  256. }
  257. #pragma page
  258. static void find_fail(int s1, int s2, int a)
  259. /* Actually compute failure transition.  We start knowing that 'a' would
  260.    normally cause us to go from state s1 to s2.  To compute the failure
  261.    value we backtrack in search of other places 'a' might go. */ 
  262. {
  263.     int on_fail;
  264.     struct kword *ktemp, kdummy, *out_copy, *kscan;
  265.  
  266.     TELLME(printf("find_fail: invoked with (%d, %d, %c)\n", s1,s2,a);)
  267.     for(;;s1 = fail_array[s1])
  268.         if (match_array[s1] == a) {
  269.             if ((on_fail = goto_array[s1].goto_state) != FAIL_STATE)
  270.                 break;
  271.         }
  272.         else if (match_array[s1] == MULTI_WAY) {
  273.             if ((on_fail = goto_array[s1].branch_table[a]) != FAIL_STATE)
  274.                 break;
  275.         }
  276.  
  277.     TELLME(printf("find_fail: on_fail is %d\n", on_fail);)
  278.     fail_array[s2] = on_fail;    
  279.  
  280.     /* merge output lists */
  281.     
  282.     /* first, make a copy of out_array[on_fail] */
  283.     if (out_array[on_fail] == NULL)
  284.         out_copy = NULL;
  285.     else {
  286.         kscan = out_array[on_fail];
  287.         out_copy = malloc(sizeof(struct kword));
  288.         out_copy->word = kscan->word;
  289.         out_copy->next = NULL;
  290.         for(kscan=kscan->next; kscan!=NULL; kscan=kscan->next) {
  291.             ktemp = malloc(sizeof(struct kword));
  292.             ktemp->word = kscan->word;
  293.             ktemp->next = out_copy->next;
  294.             out_copy->next = ktemp;
  295.         }
  296.     }
  297.  
  298.     /* now merge them */    
  299.     if ((kdummy.next = out_array[s2]) != NULL) {
  300.         ktemp = &kdummy;
  301.         for(;ktemp->next->next != NULL; ktemp = ktemp->next);
  302.         ktemp->next->next = out_copy;
  303.     }
  304.     else
  305.         out_array[s2] = out_copy;
  306. }
  307.  
  308. static void queue_add(int *queue, int qbeg, int new)
  309. /* add new to end of queue */
  310. {
  311.     int q;
  312.  
  313.     q = queue[qbeg];
  314.     if (q == 0) /* is list empty? */
  315.         queue[qbeg] = new; /* yes */
  316.  
  317.     /* no - scan to penultimate link */
  318.     else {
  319.         for(; queue[q] != 0; q = queue[q]);
  320.         queue[q] = new;    /* put this state at end of queue */
  321.     }
  322.  
  323.     /* and terminate list */
  324.     queue[new] = 0;            
  325. }
  326. #pragma page
  327. /*****************************************************************
  328.  * msrch_go() 
  329.  * Purpose: do the actual search
  330.  ****************************************************************/
  331.  
  332. void msrch_go(int (*msrch_data) (), void (*msrch_signal) (char *))
  333. /* search routine */
  334. {
  335.     int state, c, g, m;
  336.     struct kword *kscan;
  337.  
  338.     state = 0;
  339.     while ((c = msrch_data()) != EOF) {
  340.         /* what is goto(state, c)? */
  341.         for(;;) {
  342.             /* we cheat slightly in the interest of speed/simplicity.  The
  343.                machine will spend most of its time it state==0, and this state
  344.                is always a MULTI_WAY table.  Since this is a simple test, we 
  345.                make it first and try to save the calculation of an array index */
  346.  
  347.             if (state == 0 || (m = match_array[state]) == MULTI_WAY)
  348.                 g = goto_array[state].branch_table[c];
  349.             else if (m == c)
  350.                 g = goto_array[state].goto_state;
  351.             else
  352.                 g = FAIL_STATE;
  353.  
  354.             if (g != FAIL_STATE)
  355.                 break;
  356.             state = fail_array[state];
  357.         }
  358.         state = g;
  359.  
  360.         /* anything to output? */
  361.         if ((kscan = out_array[state]) != NULL)
  362.             for(;kscan != NULL; kscan = kscan->next)
  363.                 msrch_signal(kscan->word);
  364.     }
  365. }
  366. #pragma page
  367. /*****************************************************************
  368.  * msrch_end()
  369.  * Purpose: clean up when done
  370.  ****************************************************************/
  371.  
  372. void msrch_end()
  373. /* free all the arrays we created */
  374. {
  375.     int i;
  376.     struct kword *kscan;
  377.  
  378.     for (i=0; i<maxstate; i++)
  379.         if (match_array[i] == MULTI_WAY)
  380.             free(goto_array[i].branch_table);
  381.  
  382.     free(match_array);
  383.     free(goto_array);
  384.     free(fail_array);
  385.  
  386.     for (i=0; i<maxstate; i++)
  387.         if (out_array[i] != NULL)
  388.             for(kscan=out_array[i]; kscan!=NULL; kscan=kscan->next)
  389.                 free (kscan);
  390.     free(out_array);
  391. }
  392.  
  393. #pragma page
  394. /*****************************************************************
  395.  * Test driver
  396.  * 
  397.  * The routine expects a command line of the form
  398.  *    msrch file word-1 word-2 word-3 .... word-n
  399.  *
  400.  * It will then search file for all of the words on the command line.
  401.  * The results are written to stdout.  This illustrates all of the
  402.  * features of using the multisearch routines.
  403.  *
  404.  * This is an admittedly simple design--the search routine would
  405.  * certainly be faster if the character fetch routine was put
  406.  * directly into the msrch_go() module.  However, to avoid using
  407.  * application specific code in the demonstration version of these
  408.  * routines, I have coded it as a separate subroutine.
  409.  ****************************************************************/
  410.  
  411. #if TEST == 1
  412. #define BUFSIZE 200
  413.  
  414. FILE *infile;
  415. char inbuf[BUFSIZE];
  416. char *inbufptr;
  417. int linecount;
  418.  
  419. /* declare the routines that msrch_go() will use */
  420. int retrieve_char(void);
  421. void found_word();
  422.  
  423. main(int argc, char **argv)
  424. {
  425.     char infile_name[80];
  426.     struct kword *khead, *ktemp;
  427.     int i;
  428.  
  429.     if (argc < 3) {
  430.         fprintf(stderr, "Usage: msrch infile word-1 word-2 ... word-n\n");
  431.         exit(1);
  432.     }
  433.  
  434.     strcpy(infile_name, argv[1]);
  435.  
  436.     if ((infile = fopen(infile_name, "r")) == NULL) {
  437.         fprintf(stderr, "Can't open %s\n", infile_name);
  438.         exit(1);
  439.     }
  440.     linecount = 0;
  441.     inbufptr = NULL;
  442.  
  443.     /* amalgamate command line params into a list of words */
  444.     khead = NULL;
  445.     for (i=3; i<=argc; i++) {
  446.         ktemp = (struct kword *) malloc(sizeof(struct kword));
  447.         ktemp->word = argv[i-1];
  448.         ktemp->next = khead;
  449.         khead = ktemp;
  450.     }
  451.  
  452.     msrch_init(khead);    /* setup system - pass list of words */
  453.     msrch_go(retrieve_char, found_word); /* actually search.  note technique of
  454.                                             passing pointers to functions */
  455.     msrch_end();        /* clean up */
  456. }
  457.  
  458.  
  459. /* get next character from input stream.  Routine returns either 
  460.      (a) a character (as an int, and it must not have its sign extended), or
  461.      (b) EOF */
  462. int retrieve_char()
  463. {
  464.     int c;
  465.  
  466.     if (inbufptr == NULL || *(++inbufptr) == '\0') {    /* read a new line of data */
  467.         if (fgets(inbuf, BUFSIZE, infile) == NULL) {
  468.             fclose(infile);
  469.             return(EOF);
  470.         }
  471.         inbufptr = inbuf;
  472.         linecount++;
  473.     }
  474.  
  475.     c = *inbufptr;
  476.     c &= 0x00FF;    /* make sure it is not sign extended */
  477.     return (c);
  478. }
  479.  
  480. /* found_word: called by msch_go() when it finds a match */
  481. void found_word(char *word)
  482. {
  483.     int i;
  484.  
  485.     fprintf(stdout, "Line %d\n%s", linecount, inbuf);
  486.  
  487.     i = (inbufptr-inbuf) - strlen(word) + 1;
  488.     for(; i>0; i--)
  489.         fputc(' ', stdout);
  490.  
  491.     fprintf(stdout, "%s\n\n", word);
  492. }
  493. #endif
  494.